package test;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;
import java.util.stream.Collectors;
import java.util.stream.Stream;

/**
 * @author sunzhuokun
 * @date 8:53 2024/5/16
 * @description 目录删除
 * 某文件系统中有N个目录，每个目录都一个独一无二的ID。每个目录只有一个父目录，但每个父目录下可以有零个或者多个子目录，目录结构呈树状结构。
 * 假设，根目录的ID为0，且根目录没有父目录，其他所有目录的ID用唯一的正整数表示，并统一编号。
 * 现给定目录ID和其父目录ID的对应父子关系表[子目录ID，父目录ID]，以及一个待删除的目录ID，请计算并返回一个ID序列，表示因为删除指定目录后剩下的所有目录，返回的ID序列以递增序输出。
 * 注意：
 * 1、被删除的目录或文件编号一定在输入的ID序列中；
 * 2、当一个目录删除时，它所有的子目录都会被删除。
 *
 * 输入描述: 输入的第一行为父子关系表的长度m；接下来的m行为m个父子关系对；最后一行为待删除的ID。序列中的元素以空格分割，参见样例。
 *
 * 输出描述: 输出一个序列，表示因为删除指定目录后，剩余的目录ID。
 *
 * 示例1
 * 输入
 * 5
 * 8 6
 * 10 8
 * 6 0
 * 20 8
 * 2 6
 * 8
 *
 * 输出
 * 2 6
 */
public class DirectoryDeletion_目录删除 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = Integer.parseInt(sc.nextLine());
        Map<Integer, List<FileNode>> nodeMap = new HashMap<>();
        // 构建输入的文件
        for (int i = 0; i < num; i++) {
            String[] inputArr = sc.nextLine().split(" ");
            if (nodeMap.get(inputArr[1]) != null) {
                nodeMap.get(inputArr[1]).add(new FileNode(Integer.parseInt(inputArr[0])));
            } else {
                nodeMap.put(Integer.parseInt(inputArr[1]), Collections.singletonList(new FileNode(Integer.parseInt(inputArr[0]))));
            }
        }
        // 记录待删除的文件id
        int delVal = Integer.parseInt(sc.nextLine());

        // 记录需要删除的文件
        List<FileNode> removeList = new ArrayList<>();

        // 递归删除目标文件
        removeFileNode(delVal, removeList, nodeMap);

        // 生成删除后的结果
        Set<Integer> result = genResult(nodeMap, removeList);

        System.out.println(Stream.of(new ArrayList<>(result).stream().sorted().toArray()).map(String::valueOf)
                .collect(Collectors.joining(" ")));
    }

    private static Set<Integer> genResult(Map<Integer, List<FileNode>> nodeMap, List<FileNode> removeList) {
        Set<Integer> result = new HashSet<>();
        List<Integer> delValList = removeList.stream().map(fileNode -> fileNode.val).collect(Collectors.toList());
        for (Map.Entry<Integer, List<FileNode>> entry : nodeMap.entrySet()) {
            if (entry.getValue() != null && entry.getValue().size() > 0) {
                if (!delValList.contains(entry.getKey()) && entry.getKey() != 0) {
                    result.add(entry.getKey());
                }
                for (FileNode fileNode : entry.getValue()) {
                    if (!delValList.contains(fileNode.val) && fileNode.val != 0) {
                        result.add(fileNode.val);
                    }
                }
            }
        }
        return result;
    }

    private static void removeFileNode(int delVal, List<FileNode> removeList, Map<Integer, List<FileNode>> nodeMap) {
        removeList.add(new FileNode(delVal));
        if (nodeMap.get(delVal) != null) {
            for (FileNode fileNode : nodeMap.get(delVal)) {
                removeFileNode(fileNode.val, removeList, nodeMap);
            }
        }
    }

    static class FileNode {
        int val;

        List<FileNode> subList;

        FileNode(int val) {
            this.val = val;
        }

        public void addSub(FileNode node) {
            if (subList == null) {
                subList = new ArrayList<>();
            }
            subList.add(node);
        }

        public void delete(int value) {
            if (subList != null) {
                for (int i = 0; i < subList.size(); i++) {
                    if (subList.get(i).val == value) {
                        subList.remove(i);
                        break;
                    }
                }
            }
        }
    }


}
